Infinitude of Primes

The proof given below was originally formulated by Euclid. Another famous proof comes about by proving the stronger result that the sum of reciprocals of primes diverges.

Proof

Assume, by way of contradiction, that the set \(P = \{p_{1}, \dots, p_{n}\}\) is an exhaustive collection of primes.

Then, define

There are two cases to consider. The first is where \(x\) is prime. However \(x > \max(P)\) and hence we have a prime \(x \notin P\), a contradiction.

If \(x\) is composite then it is divisible by a prime \(p_{i} \in P\). Calculating this division gives

However, \(p_{i} \mid x \implies \frac{x}{p_{i}} \in \mathbb{Z}\), and the product on the right hand side is also an integer. Given that \(2\) is the smallest prime, we have a contradiction of a non integer \(\frac{1}{p_{i}}\) plus an integer is an integer.

Here is a similar, alternate proof.

Proof

Let \(n > 1\) be an integer, and consider \(n! + 1\). Suppose a prime \(p\) divides \(n! + 1\). If \(p \leq n\), then \(p \mid n!\) and hence \(p \mid n! + 1 - n! = 1\), a contradiction on \(p\) being prime. As such, any prime factor of \(n! + 1\) must be greater than \(n\). This means that there exists arbitrarily large primes, since \(n! + 1\) will always have a prime factor (using a weaker form of the fundamental theorem of arithmetic).